package com.xzx.list;

/**
 * @author xinzhixuan
 * @version V1.0.0
 * @date 2021/3/14
 **/
public class LinkedList implements List{
    private Node head;
    private int size;

    @Override
    public List makeEmpty() {
        head = new Node(0, null);
        size = 0;
        return this;
    }

    @Override
    public Integer findKth(int k) {
        if (k < size && k >=0) {
            Node temp = head;
            for (int i =0; i <=k; i++) {
                temp = temp.getNext();
            }
            return temp.getData();
        }
        throw new RuntimeException("不存在位序");
    }

    @Override
    public int find(Integer x) {
        Node temp = head;
        int index = -1;
        while (temp.getNext() != null) {
            index ++;
            temp = temp.getNext();
            if (temp.getData() == x) {
                return index;
            }
        }
        return -1;
    }

    @Override
    public void insert(Integer x, int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("位置不合法");
        }

        Node newNode = new Node(x, null);
        Node temp = head;

        for(int i = 0; i < index; i++) {
            temp = temp.getNext(); // 第index位置的元素的前一个元素
        }

        newNode.setNext(temp.getNext());//第index位置的元素
        temp.setNext(newNode);
        size++;
    }

    @Override
    public void delete(int index) {
        if (size == 0) {
            throw new RuntimeException("表空");
        }

        if (index < 0 || index > size) {
            throw new RuntimeException("位置不合法");
        }

        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();// 第index元素的前一个元素
        }
        Node indexNode = temp.getNext();
        temp.setNext(indexNode.getNext());
        size--;
    }

    @Override
    public int length() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node temp = head;
        while (temp.getNext() != null) {
            builder.append(temp.getNext().getData() + ",");
            temp = temp.getNext();
        }
        return builder.toString();
    }
}

class Node {
    private int data;
    private Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}
